package Ruanj1;

public class PrintPrimes {
    public static void main(String[] args) {
        // 测试基础版本
        long startTime1 = System.currentTimeMillis();
        System.out.println("=== 基础版本 ===");
        printPrimes(1, 20000, 5);
        long endTime1 = System.currentTimeMillis();
        long basicTime = endTime1 - startTime1;

        // 测试优化版本
        long startTime2 = System.currentTimeMillis();
        System.out.println("\n=== 优化版本 ===");
        printPrimesOptimized(1, 20000, 5);
        long endTime2 = System.currentTimeMillis();
        long optimizedTime = endTime2 - startTime2;

        System.out.println("基础版本耗时: " + basicTime + "ms");
        System.out.println("优化版本耗时: " + optimizedTime + "ms");
    }
    public static void printPrimes(int start, int end, int perLine) {
        int count = 0;
        for (int i = start; i <= end; i++) {
            if (isPrime(i)) {
                System.out.printf("%-8d", i);
                count++;
                if (count % perLine == 0) {
                    System.out.println();
                }
            }
        }

        System.out.println("\n总共找到 " + count + " 个素数");
    }
    // 优化版本
    public static void printPrimesOptimized(int start, int end, int perLine) {
        int count = 0;
        for (int i = start; i <= end; i++) {
            if (isPrimeOptimized(i)) {
                System.out.printf("%-8d", i);
                count++;
                if (count % perLine == 0) {
                    System.out.println();
                }
            }
        }
        System.out.println("\n总共找到 " + count + " 个素数");
    }
    public static boolean isPrime(int num) {
        if (num <=1) {
            return false;

        }
        if (num <=3) {
            return true;
        }
        if (num%2==0 || num%3==0) {
            return false;
        }
        for (int i=3; i<= Math.sqrt(num); i+=2) {
            if (num % i ==0) {
                return false;
            }
        }
        return true;
        }

    // 优化思路：所有大于3的素数都可以表示为 6k±1 的形式
    public static boolean isPrimeOptimized(int num) {
        if (num <=1) return false;
        if (num <=3) return true;
        if (num%2 ==0 || num%3==0) return false;

        // 只检查 6k±1 形式的除数
        for (int i=5; i<= Math.sqrt(num); i+=6) {
            if (num % i==0 || num % (i+2) ==0) {
                return false;
            }
        }
        return true;
    }
}
/*
最费时的函数：isPrime(),耗时：50ms
优化的算法只检查6k±1形式的除数，减少检查次数，耗时：23ms
*/